COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	CS106
C00006 ENDMK
C⊗;
CS106
		
Example:

We have a string in the character array  S[1..N]  which we want to test for being
a legitimate Pascal assignment command.  We will simplify the problem by only
allowing simple variables, positive integer constants, addition, multiplication,
and parentheses. The defining rules are:

(1) A command  (C)  is a variable  (V), followed by `:=`, followed by an
expression  (E), followed by a semicolon.  In abbreviated form  C ~ V:=E;

(2) An expression is a sum of one or more terms (to be defined next).  That is,
it is either a term, or is a (shorter) expression followed by  `+`  followed by
a (shorter) term.
			E ~ T or E + T

(3) A term is a product of one or more factors  (F)  (to be defined next):

			T ~ F or T * F

(4) A factor is a number  (N), a variable  (V), or an expression with parentheses
around it.		
			F ~ N or V or (E).

(5) A number is a digit or ...

(6) A variable is a letter or ...

Using dynamic programming, we will test every segment (substring) of the string
to see whether it belongs to one or more of the above types.  For each type, we
have a boolean array, indexed by the endpoints of the segments, to record whether
each segment belongs to the type.  For example, the array element  V[START, LENGTH]
will be true if  S[START..START+LENGTH-1]  is a variable by the above definitions.

The algorithm initializes the arrays to false.  Then the letter and digit arrays are
set true where appropriate:

	FOR I:=1 TO N DO
		BEGIN
		IF ('A'<=S[I]) AND (S[I]<='Z')
			THEN L[I,1]:=TRUE
		ELSE IF ('O'<=S[I]) AND (S[I]<='9')
			THEN D[I,1]:=TRUE
		END

Then the main iteration tests each segment, in order of increasing length:

	FOR LENGTH:=1 TO N DO
	FOR START:=1 TO N+1-LENGTH DO

		BEGIN
		IF L[START,LENGTH]THEN
			V[START,LENGTH:=TRUE;
		FOR SHORTER:=1 TO LENGTH-1 DO
			IF V[START,SHORTER] AND
				L[START+SHORTER,LENGTH-SHORTER]
			THEN V[START,LENGTH]:=TRUE;

		IF V[START,LENGTH]THEN
			F[START,LENGTH]:=TRUE;

		IF E[START+1.;LENGTH-2]AND
			(S[START]='(') AND (S[START+LENGTH-1=')')
			THEN F[START,LENGTH]:=TRUE

		FOR SHORTER:=1 TO LENGTH-2 DO
			IF T[START,SHORTER] AND (S[START+SHORTER]='*')
				AND F[START+SHORTER+1,LENGTH-SHORTER-1]

			THEN T[START,LENGTH]:=TRUE

			etc.
		END


When done, we check whether  C[1,N]  is true.  If so, the string is a correct
assignment command.  Nothing to it.